package com.leetcode.offer;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author zfl
 * @Classname GetLeastNumber
 * @Description 最小的k个数
 * @Date 2020/11/8 10:06
 */
public class GetLeastNumber {

    /**
     * @param arr
     * @param k
     * @return
     * 执行用时：8 ms, 在所有 Java 提交中击败了61.64%的用户
     * 内存消耗：39.5 MB, 在所有 Java 提交中击败了94.94%的用户
     */
    public static int[] getLeastNumber(int[] arr, int k) {
        Arrays.sort(arr);
        int[] nums = new int[k];
        int len = arr.length;
        for (int i = 0; i < k; i++) {
            nums[i] = arr[i];
        }
        return nums;
    }

    /**
     * @param arr
     * @param k
     * @return
     * 运算时间很慢
     */
    public static int[] getLeastNum(int[] arr, int k) {
        int len = arr.length,temp = 0;
        int[] nums = new int[k];
        for (int i = 0; i < k; i++) {
            for (int j = i + 1; j < len; j++) {
                if(arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            nums[i] = arr[i];
        }
        return nums;
    }

    /**
     * @param n
     * @param m
     * 不能直接调用函数，值传递
     */
    public static void exch(int n, int m) {
        int temp = n;
        n = m;
        m = temp;
    }

    public static int[] getLeastNums(int[] arr, int k) {
        if(k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 最后一个元素表示我们要找的下标为k - 1的数
        return quickSearch(arr,0,arr.length - 1,k - 1);
    }

    private static int[] quickSearch(int[] nums, int lo, int hi, int k) {
        // 快排切分一次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数
        int j = partition(nums,lo,hi);
        if(j == k) {
          return Arrays.copyOf(nums,j + 1);
        }
        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段
        return j > k ? quickSearch(nums,lo,j - 1,k) : quickSearch(nums,j + 1,hi,k);
    }

    private static int partition(int[] nums, int lo, int hi) {
        int v = nums[lo];
        int i = lo,j = hi + 1;
        while (true) {
            while (++i <= hi && nums[i] < v);
            while (--j >= lo && nums[j] > v);
            if(i >= j) {
                break;
            }
            int t = nums[j];
            nums[j] = nums[i];
            nums[i] = t;
        }
        nums[lo] = nums[j];
        nums[j] = v;
        return j;
    }

}
